13.4 進行性の保証
進行性保証
競合するスレッドの実行が進むことへの保証
不可分プリミティブごとにサポートする保証の度合いが異なる
強い順:
多分こっちの順番が正しい
wait-free
すべてのスレッドが常に進行できる
lock-free
いずれかのスレッドが有限ステップで処理を終了する
その終了する処理を無限回繰り返せる
obstruction-free
十分に長い期間独立して実行させると、どのスレッドも有限のステップ数で終了する
ただし、独立して実行とは、1つのスレッドを選択してその他のスレッドをサスペンドした状態で選択したスレッドを進行させること
現実のシステムでは、メモリの制約などにより、保証はほぼ常に条件付き
スレッド間の助け合い
wait-freeアルゴリズム中に現れる概念
スレッドt2の進行がt2より(何らかの基準で)進んでいるスレッドt1の進行を妨害するとき、t2がt1の進行を手助けした後にt2を進行する
スレッド数が有界の場合
単位量の仕事までに必要な手助けの総量も有界
したがって、仕事の合計時間も有界
仕事の合計時間の上界が大きいかもしれない
単位量の仕事に要する時間も(wait-freeなので)長くなりがち
で？気持ちがわからん意味不明
合意問題の場合には時間的オーバーヘッドの小さいwait-freeアルゴリズムがある
code: wait-free-consensus.py
shared winner = -1 # 最初に到達したスレッドのID
me = myThreadId
def decide(v):
CompareAndSwap(&winner, -1, me)
進行性保証の達成
obstruction-free性
wait-freeより簡単
実際にうまく実行するためにはスケジューラによる協調が必要となりうる
競合した際に、0からTまでのランダムな時間停止してから再試行する
競合するたびにTを増やす
確率的にどのスレッドもいずれ成功する
lock-free性
さらに容易
ほんまか
少なくとも1つの競合スレッドが進行すればよい
特定のスレッドが永久にスタベーションしてもよい
進行性保証と並行GC
並行GC (concurrent collector)
GCの一部をミューテータスレッドの走行中に実行する
一般にコレクタスレッドを複数用いる
並列GC (parallel collector)
コレクタが同時に複数のスレッドを用いる
GC中はミューテータスレッドを停止する
並行GCにおいて、コレクタスレッドが他のコレクタスレッドやミューテータスレッドと干渉し合いうる
並行GCのコレクタがサポートすべきこと:
ルートから到達可能なオブジェクトは回収しない
ミューテータの書き換えを妨害しない
いくらかのゴミオブジェクトを回収する
回収率はアルゴリズムによる
完全なGCアルゴリズムは、十分な回数のGCによりすべてのゴミを回収する
GC中にオブジェクトが到達不能になった場合に対処する
そのオブジェクトはGC中に割り付けられたばかりかもしれない
停止性
GC中に新しいオブジェクトが増えたり構造(オブジェクトグラフ)が変化する
ミューテータが増やす仕事の速度にコレクタが追いつけるか
スレッドの進行
lock-freeだと1つのスレッドが永久に失敗し続ける可能性がある
ライブロック (livelock): 2つの競合するスレッドが互いの進行を無期限に妨害し続ける
GCのフェーズごとにサポートすべき進行性保証が異なる
実用的には一部のフェーズではストップザワールド式の停止が必要かもしれない
トレードオフ
完全なwait-free
コーディングの複雑さ・バグの可能性の増大
ミューテータがwait-freeと感じるためにはGCの完了を待たなくてもミューテータの割り付けが可能なくらいに十分に速いメモリ回収が必要
そのためには、ヒープサイズ・生きているデータの最大サイズ・割り付け速度・GC速度の全体的なバランスが必要
詳しくは19章で
それまでの間のアルゴリズムの大半の進行性保証は弱い
lock-freeが一部のフェーズで保証される程度
実装が容易
この程度で許容できる場合も多い